#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <stack>
#define MAXSIZE 1000
using namespace std;

//顺序表结构体
typedef struct SqList
{
    int data[MAXSIZE];
    int length;
} SqList;

//单链表结构体
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode;

//顺序栈
typedef struct SqStack
{
    int top;
    char data[MAXSIZE];
} SqStack;
typedef struct ISqStack
{
    int top;
    int data[MAXSIZE];
} ISqStack;

//链栈 出战相当于去掉第一个结点，入栈：头插法插入结点
typedef struct LStack
{
    struct LNode *next;
    char data;
} LStack;

//顺序表创建的队列
typedef struct SQueuq
{
    int data[MAXSIZE];
    int front, rear;
} queuq;

//链表创建队列
typedef struct LQueue
{
    LNode *front, *rear;
} LQueue;

/********************************顺序栈********************************/
//初始化
void InitStack(SqStack &S)
{
    S.top = -1;
}
//判空
bool isEmpty(SqStack S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}
bool isEmptyInt(ISqStack S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}
//进栈
bool push(SqStack &S, char x)
{
    if (S.top == MAXSIZE)
        //栈满
        return false;
    S.data[++S.top] = x;
    return true;
}
bool pushI(ISqStack &S, int x)
{
    if (S.top == MAXSIZE)
        //栈满
        return false;
    S.data[++S.top] = x;
    return true;
}
//出栈,栈顶元素赋值给x
bool pop(SqStack &S, char &x)
{
    if (S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}
bool popI(ISqStack &S, int &x)
{
    if (S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}
//读栈顶元素 赋值给x
char getTop(SqStack S)
{
    if (S.top == -1)
        return '\0';
    return S.data[S.top];
    ;
}

bool isLower(char string0, char string1)
{
    int a, b;
    if (string0 == '+' || string0 == '-')
        a = 1;
    if (string0 == '*' || string0 == '/')
        a = 2;
    if (string0 == '(' || string0 == ')')
        a = 3;
    if (string1 == '+' || string1 == '-')
        a = 1;
    if (string1 == '*' || string1 == '/')
        a = 2;
    if (string1 == '(' || string1 == ')')
        a = 3;
    return a < b;
}

/**
 * 计算器
 * n表示字符串数组的长度。字符串数组str只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
 * 整数和运算符之间用一个空格分隔。没有非法表达式。输出计算结果。(精确到小数点后2位)
 * eg: n=5 str[]={"1 + 2"} 输出：3.00
 * n=18 str[]={"4 + 2 * 5 - 7 / 11"}输出13.36
 * ans：
 *  遍历字符串 s，并用变量 preSign 记录每个数字之前的运算符，对于第一个数字，
 *  其之前的运算符视为加号。每次遍历到数字末尾时，根据 preSign 来决定计算方式：
 *      加号：将数字压入栈；
 *      减号：将数字的相反数压入栈；
 *      乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。
 * 补充：int isdigit(int c); 判断参数c是否为数字，返回值：0-不是数字，非0-是数字。
 */
double calculate(char* s) {
    int n = strlen(s);
    double *stk = (double*)malloc(n * sizeof(double));
    int top = 0;
    char preSign = '+';
    int num = 0;
    for (int i = 0; i < n; ++i) {
        if (isdigit(s[i])) {
            num = num * 10 + (int)(s[i] - '0');
        }
        if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {//若不是符号，或者当前遍历的是倒数第二个元素
            switch (preSign) {
                case '+':
                    stk[top++] = num;
                    break;
                case '-':
                    stk[top++] = -num;
                    break;
                case '*':
                    stk[top - 1] *= num;
                    break;
                default:
                    stk[top - 1] /= num;
            }
            preSign = s[i];
            num = 0;
        }
    }
    double result = 0;
    for (int i = 0; i < top; i++) {
        result += stk[i];
    }
    free(stk);
    return result;
}

/**
 * 给出一个由左右花括号、中括号、小括号组成的字符串，判断给定字符串的括号是否匹配，括号之间没有优先级
 */
bool isLegalBracket(char str[], int n) // n表示字符串长度,str存字符串
{
    char ch[MAXSIZE];
    //字符栈
    int top = -1;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == '{' || str[i] == '[' || str[i] == '(')
            //左括号直接入栈
            ch[++top] = str[i];
        //如果执行else if 那么必然是右括号，所以如果符号栈空，必然是失配 
        //四种失配情况，栈空失配，大括号失配，中括号失配，小括号失配
        else if (top == -1 || 
        (str[i] == '}' && ch[top] != '{') || 
        (str[i] == ']' && ch[top] != '[') || 
        (str[i] == ')' && ch[top] != '('))
            return 0;
        else
            top--;
    }
    if (top != -1)
        return 0;
    return 1;
}

/**
 * 有一个字符串，由左括号'('和右括号')'组成，保证输入的括号匹配性是合法的。
 * 每一对括号都有价值，深度 为1的括号，价值为1，深度为2的括号价值为2，求该序列的所有对括号的价值和。
 * 例如："((()))"，这三对 括号的深度分别为1、2、3，则价值和为6。
 *      "()(())"，这三对括号的深度分别为1、1、2，则价值和为4.
 *  eg: 输入："((()))(())" 输出：9
 *      输入："()()()()"输出4
 */
int bracketValue()
{
    int ans;  //本题的答案
    int deep; //记录深度
    char str[MAXSIZE];
    scanf("%s", str);
    int len = strlen(str); //输入的字符串的长度
    for (int i = 0; i < len; i++)
    {

        if (str[i] == '(')
            //如果是左括号则深度+1
            deep++;
        else //右括号则计算该对括号的价值，并深度-1
        {
            ans += deep;
            deep--;
        }
    }
    cout << ans << endl;
    return 0;
}

/**
 * 栈模拟：给定输入序列和输出序列，判断通过栈能否得到输出序列，对于输入序列，随时可以入栈或者出栈
 * 思路：1.创建一个数组，作为栈
 *      2.遍历数组 pushed，将 pushed 的每个元素依次入栈；
 *      3.每次将 pushed 的元素入栈之后，如果栈不为空且栈顶元素与 popped 的当前元素相同，则将栈顶元素出栈，
 *   同时遍历数组 popped，直到栈为空或栈顶元素与 popped 的当前元素不同。
 *      4.如果栈为空，返回 true，否则，返回false
 */
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
    int *stk = (int *)malloc(sizeof(int) * pushedSize);
    int top = 0;
    for (int i = 0, j = 0; i < pushedSize; i++) {
        stk[top++] = pushed[i];
        while (top > 0 && stk[top - 1] == popped[j]) {
            top--;
            j++;
        }
    }
    free(stk);
    return top == 0;
}

/**
 * 用两个栈来实现队列，请写出入队和出队算法。
 * 思路：
 * 将一个栈当作输入栈，用于压入 appendTail 传入的数据；另一个栈当作输出栈，用于 deleteHead 操作。
 * 每次 deleteHead 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，
 * 这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序
*/
typedef struct {
    int* stk;
    int stkSize;
    int stkCapacity;
} Stack;

Stack* stackCreate(int cpacity) {
    Stack* ret = (Stack*)malloc(sizeof(Stack));
    ret->stk = (int*)malloc(sizeof(int) * cpacity);
    ret->stkSize = 0;
    ret->stkCapacity = cpacity;
    return ret;
}

void stackPush(Stack* obj, int value) {
    obj->stk[obj->stkSize++] = value;
}

void stackPop(Stack* obj) {
    obj->stkSize--;
}

int stackTop(Stack* obj) {
    return obj->stk[obj->stkSize - 1];
}

bool stackEmpty(Stack* obj) {
    return obj->stkSize == 0;
}

void stackFree(Stack* obj) {
    free(obj->stk);
}

typedef struct {
    Stack* inStack;
    Stack* outStack;
} CQueue;

CQueue* cQueueCreate() {
    CQueue* ret = (CQueue*)malloc(sizeof(CQueue));
    ret->inStack = stackCreate(10000);
    ret->outStack = stackCreate(10000);
    return ret;
}

void in2out(CQueue* obj) {
    while (!stackEmpty(obj->inStack)) {
        stackPush(obj->outStack, stackTop(obj->inStack));
        stackPop(obj->inStack);
    }
}

void cQueueAppendTail(CQueue* obj, int value) {
    stackPush(obj->inStack, value);
}

int cQueueDeleteHead(CQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        if (stackEmpty(obj->inStack)) {
            return -1;
        }
        in2out(obj);
    }
    int x = stackTop(obj->outStack);
    stackPop(obj->outStack);
    return x;
}

void cQueueFree(CQueue* obj) {
    stackFree(obj->inStack);
    stackFree(obj->outStack);
}

/**
 * 将一个十进制的正整数n转换为k进制的数
 * 思路：定义一个栈，若a = n%k，将a入栈，n/=k，如此循环直到a = 0；然后将
 */
void tenToK(int n, int k)
{
    int ansStack[MAXSIZE];
    int top = -1;
    while (n)
    {
        ansStack[++top] = n % k;
        n /= k;
    }
    while (top != -1)
    {
        printf("%d", ansStack[top]);
        top--;
    }
}

/**
 * 用两个栈来实现队列，请写出入队和出队算法。
 */
int enQueue(ISqStack &s1, ISqStack &s2, int x)
{
    int y;
    if (s1.top == MAXSIZE - 1) // s1栈满
    {
        if (!isEmptyInt(s2)) // s2栈不是空
            return 0;     //不能进队
        else
        {
            while (!isEmptyInt(s1)) //先把s1的元素全转到s2中
            {
                popI(s1, y);
                pushI(s2, y);
            }
            pushI(s1, x); //再把元素入栈s1
        }
    }
    else
        pushI(s1, x); //直接入栈s1
    return 1;
}
int deQueue(ISqStack &s1, ISqStack &s2, int &x)
{
    if (isEmptyInt(s1) && isEmptyInt(s2))
        return 0;
    int y;
    if (!isEmptyInt(s2))
        popI(s2, x);
    else
    {
        while (!isEmptyInt(s1))
        {
            popI(s1, y);
            pushI(s2, y);
        }
        popI(s2, x);
    }
    return 1;
}

/**
 * 火车站：
 * 有一列火车车厢进站，可以通过中转站改变出站顺序，
 * 现在的问题是，给定入站顺序和出栈顺序后，请问该站的容纳量至少为多少节车厢？
 * 例如，进站顺序为ABCD，出站顺序为DCBA，则该站台的容纳量至少为4.保证出站顺序合法
 * 第一行输入n，表示总共有n节车厢
 * 第二行输入n个字母表示进站的车厢序列
 * 第三行输入n个字母表示出站的车厢序列输出x表示站台的容纳量
 * 输入： 5 ABCDE CBEDA 输出：3
 * 思路：
 * 方法一： 1.定义一个长度为n的char数组，作为栈，和当前车站容量temp，以及答案ans
 *          2.遍历in，并将数据存入栈中
 *          3.若栈顶元素与out中的元素相同这循环弹出栈中元素，直到栈空或者不相等为止
 *          4.若栈空，则将temp和ans比较若temp>ans,则更新ans为temp。
 *          5.若栈空temp=0
*/
int minTrainStations(int n, char* in, char* out){
    char* stk = (char*)malloc(n * sizeof(char));
    int ans = 0, temp = 1, top = 0;
    for (int i = 0,j = 0; i < n; i++)
    {
        stk[top++] = in[i];
        temp++;
        while (top > 0 && stk[top - 1] == out[j])
        {
            top--;
            temp--;
            j++;
        }
        if (temp > ans)
            ans = temp;
    }
    return ans;
}

/**
 * 求后缀表达式的值
 * 思路：使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：
 *          1.如果遇到操作数，则将操作数入栈；
 *          2.如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，
 * 使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
*/
bool isNumber(char* token) {
    return strlen(token) > 1 || ('0' <= token[0] && token[0] <= '9');//长度大于1的肯定是数字
}
int evalRPN(char** tokens, int tokensSize) {
    int n = tokensSize;
    int *stk=(int*)malloc(n * sizeof(int)), top = 0;
    for (int i = 0; i < n; i++) {
        char* token = tokens[i];
        if (isNumber(token)) {
            stk[top++] = atoi(token);
        } else {
            int num2 = stk[--top];
            int num1 = stk[--top];
            switch (token[0]) {
                case '+':
                    stk[top++] = num1 + num2;
                    break;
                case '-':
                    stk[top++] = num1 - num2;
                    break;
                case '*':
                    stk[top++] = num1 * num2;
                    break;
                case '/':
                    stk[top++] = num1 / num2;
                    break;
            }
        }
    }
    return stk[top - 1];
}

/********************************链栈(默认带头结点)********************************/
//初始化
void InitLStack(LStack *L)
{
    L = (LStack *)malloc(sizeof(LNode));
    L->next = NULL;
}
//判空
bool isEmptyL(LStack *L)
{
    if (L->next == NULL)
        return 1;
    else
        return 0;
}
//进栈
void pushL(LStack *L, int x)
{
    LNode *p;
    p = (LNode *)malloc(sizeof(LNode));
    p->next = NULL;
    p->data = x;
    //头插法
    p->next = L->next;
    L->next = p;
}
//出栈
bool popL(LStack *L, int &x)
{
    if (L->next == NULL)
        return 0;
    LNode *p;
    p = L->next;
    x = p->data;
    L->next = p->next;
    //删除链表第一个结点
    free(p);
    return 1;
}

/********************************队列********************************/

int main()
{
    //计算器
    // char str[]={"4 - 7 / 11 + 2 * 5"};
    // double ans = calculate(str);
    // printf("%.2lf",ans);
    //火车站
    // int n;
    // cin>>n;
    // char* in = (char*)malloc(n * sizeof(char));
    // char* out = (char*)malloc(n * sizeof(char));
    // cin>>in;
    // cin>>out;

    char in[4]={'A','B','C','D'};
    char out[4]={'D','C','B','A'};
    // char in[5]={'A','B','C','D','E'};
    // char out[5]={'C','B','E','D','A'};
    int ans = minTrainStations(4, in, out);
    cout<<ans<<endl;
    // system("pause");
    return 0;
}